#include "../common/AVLTreeNode.h"

/* 平衡二叉搜索树执行旋转操作，使该子树重新恢复平衡 */
AVLTreeNode* rotate(AVLTreeNode* node) {
    int _balanceFactor = balanceFactor(node);
    if (_balanceFactor > 1) {
        if (balanceFactor(node->left) >= 0) {
            return rightRotate(node);
        } else {
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    }
    if (_balanceFactor < -1) {
        if (balanceFactor(node->right) <= 0) {
            return leftRotate(node);
        } else {
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    return node;
}

/* 右旋操作 */
AVLTreeNode* rightRotate(AVLTreeNode* node) {
    AVLTreeNode* child = node->left;
    AVLTreeNode* grandChild = child->right;
    child->right = node;
    node->left = grandChild;
    updateHeight(node);
    updateHeight(child);
    return child;
}

/* 左旋操作 */
AVLTreeNode* leftRotate(AVLTreeNode* node) {
    AVLTreeNode* child = node->right;
    AVLTreeNode* grandChild = child->left;
    child->left = node;
    node->right = grandChild;
    updateHeight(node);
    updateHeight(child);
    return child;
}
